//
// Created by 谢哲 on 2021/5/9.
//

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

constexpr unsigned long long mod = 10000ull;

vector<vector<int>> dp_data;
unsigned long long dfs(int left, int right) {
    if (left < 0 || right < 0) {
        return 0ull;
    }
    if (left == 0 && right == 0) {
        return 1ull;
    }
    if (dp_data[left][left-right+1]>=0) return (unsigned long long)dp_data[left][left-right+1];
    unsigned long long ans = 0ull;
    ans += dfs(left-2, right-2);
    if (left==right+1) {
        ans += dfs(left-2, right-1)+dfs(left-3,right-2);
    }
    else if (right==left+1) {
        ans += dfs(left-1, right-2)+dfs(left-2,right-3);
    }
    else if (left==right) {
        ans += dfs(left-1, right-1)+dfs(left-1,right-2)+dfs(left-2,right-1);
    }
    ans = ans % mod;
    dp_data[left][left-right+1] = (int)ans;
    return ans;
}


int main() {
    int N;
    cin >> N;
    dp_data.resize(N+1, vector<int>(3, -1));
    cout << dfs(N, N);

    return 0;
}
